The present invention relates to an apparatus and a method for receiving data and, more particularly, to a data receiver and a data receiving method for receiving multi-component signals representing values for several data bits.
In the U.S.A., digital broadcasting bas already been started. Also in Europe, the organization for standardization xe2x80x9cDigital Video Broadcasting (DVB)xe2x80x9d has been formed to introduce digital TV broadcasting and its standard system is now being made. Such digital broadcasting is described, for example, in xe2x80x9cEurope set to start digital satellite broadcasting in 1996 after successful U.S. nationwide servicesxe2x80x9d, NJKKEI ELECTRONICS 1.15, 1996 (No. 653), pp. 139-151.
In digital broadcasting and in other types of data transmission, it is desirable to minimize the power in the signal. This in turn reduces the ratio of signal power to noise power, and increases the probability of transmission errors. An error-correcting code is used to obtain a coding gain which compensates for this effect. Ordinarily, in a system using such a method, error-correcting coding is performed on the transmitting side while error-correcting decoding is performed on the receiving side.
A convolutional code is particularly advantageous for transmission on a communication path with a low signal power to noise power ratio (S/N ratio). As further explained below, a convolutional code effectively spreads the information contained in each bit of the original message into several bits of the transmitted signal. The receiver determines the value of each original bit from the received signals representing the bits of the transmitted signal. Because the transmitted signal contains redundant information, the original bit values can still be determined with good accuracy even if some of the bit values in the transmitted signal are corrupted by noise in the transmission path. The receiver can use a probabilistic or xe2x80x9csoftxe2x80x9d decoding scheme. If a most likely path decoding method such as Viterbi decoding is used, soft decision decoding can be performed easily and a high coding gain can be obtained.
In a xe2x80x9cpuncturedxe2x80x9d convolutional code, a sequence of bits output from a convolutional encoder is thinned out by deleting some of the bits in accordance with a certain rule. Thus, the redundancy introduced by convolutional encoding is reduced, and a plurality of code rates can be achieved easily.
It is also possible to improve tolerance to noise in a transmission path by diffusing bits of an encoded signal, such as the bits of a code sequence output from a punctured convolutional code encoder, in accordance with a certain rule. xe2x80x9cDiffusingxe2x80x9d in this context refers to shuffling or reordering the bits.
FIG. 9 shows an example of a transmitter proposed in accordance with the standard DVB-T for DVB ground wave television. This transmitter uses a punctured convolutional code, bit diffusion and a quadrature phase-shift keying (QPSK) system.
In the example shown in FIG. 9, serial data output from an information source 1 is input to a convolutional encoder 2, and mother code sequences X and Y are generated by the encoder 2. Each of X and Y represents a 1-bit code sequence. Thus, each bit of original data from information source 1 results in generation of two bits of mother code data; one bit in sequence X, and one bit in sequence Y. Stated another way, in this example, the code rate of convolutional encoder 2 is set to 1/2.
FIG. 10 shows an example of the convolutional encoder 2. The particular encoder 2 is not arranged in accordance with the DVB-T standard; it is a simple encoder intended for explanation of the principle of convolutional processing. In this example, 1-bit serial data output from an information source 1 is input through a terminal 21, delayed one clock cycle by each of delay circuits 22 and 23 and thereafter output to adder circuits 24 and 25. The output from terminal 21 and the output from delay circuit 22 are also supplied to the adder circuit 24. Adder circuit 24 adds these groups of data together (by exclusive OR operation) and outputs the result of this addition as data X through a terminal 26. Adder circuit 25 adds the output from the terminal 21 and the output from the delay circuit 23 together (by exclusive OR operation) and outputs the result of this addition as data Y through a terminal 27.
In this example, the two mother code bits X and Y which are obtained when one original bit is input at terminal 21 will depend on the internal state of the delay circuits 22 and 23 prior to arrival of that original bit. The state of the delay circuits 22 and 23 in turn will depend upon the values of the bits which were previously supplied through terminal 21. Stated another way, the information in each bit of the original message is spread among several bits of the mother code sequences. In this example, the constraint length is 3, the number of internal delay elements is 2, the number of states is 4, and the code rate is 1/2.
FIG. 11 is a state diagram showing state transitions of the convolutional encoder shown in FIG. 10. If an original code bit with value 0 is input through terminal 21 when the state is 00 (when each of the outputs of the delay elements 22 and 23 is 0), (XY)=(00) is output through the terminals 26 and 27. That is, mother code bit 0 is output as data X through terminal 26, whereas mother code bit 0 is output as data Y through terminal 27. The state is also 00 after the transition resulting from the 0 input; the outputs of each of delay elements 22 and 23 remain 0. In the case where 1 is input when the state is 00, (XY)=(11) is output and the state changes to 10. In the case where 0 is input when the state is 01, (XY)=(11) is output and the state changes to 00. In the case where 1 is input when the state is 01, (XY)=(00) is output and the state changes to 10.
The inputs and outputs associated with these and other states are shown in FIG. 11 as expressions such as xe2x80x9c1/01xe2x80x9d, denoting input/outputs. In each such expression, the first digit represents the input, whereas the second digit represents the X output resulting from that input and the last digit represents the Y output resulting from the input.
The mother code sequences X and Y provided by convolutional encoder 2 are input to a bit erase circuit 3, which performs bit erasing in accordance with a predetermined rule, and forms the remaining bits into a serial bit stream constituting a punctured convolutional code message. The bit erase circuit 3 erases data at predetermined positions in the mother code sequences (XY), in accordance with an erase map:
X: 10
Y: 11
Bits corresponding to 1 in the erase map are transmitted but bits corresponding to 0 in the map are not transmitted (erased). Stated another way, every other bit in the X mother code sequence is omitted from the serial bit stream formed by the bit erase circuit. Thus, if the outputs of convolutional encoder 2 in response to two successive inputs are X1,Y1 in response to the first input and X2,Y2 in response to the next input, the bit erase circuit will transmit a serial stream X1Y1Y2. The same series of operations is repeated during every two successive clock cycles of the apparatus.
The bit erase circuit reduces redundancy in the coded message and thus changes the code rate. Considering the convolutional encoder and the bit erase circuit together, the number of bits in the original message input to the convolutional encoder 2 is 2 and the number of bits in the punctured convolutional code output from the bit erase circuit 3 is 3, so that the code rate is 2/3.
The bit stream or serialized punctured convolutional code sequence output from the bit erase circuit 3 is input to a serial-parallel converter 4. Serial-parallel converter 4 converts one input data sequence X1,Y1,Y2, . . . into two data sequences (x, y).
The data sequences x and y from converter 4 undergo bit diffusion in bit diffusion circuits 5-1 and 5-2. The order of bits is in each sequence is diffusively changed (made complex). Each of the bit diffusion circuits 5-1 and 5-2 performs bit diffusion by changing the order of the bits in data sequence x or y in accordance with a predetermined rule. Ordinarily, the rules applied by. the bit diffusion circuits 5-1 and 5-2 are different from each other.
In an example of such bit diffusion, M bits of input data is assumed to be one block, and a suitable value s is set. The bit diffusion process is performed by replacing a vector formed of an M-bit input sequence:
(B0, B1, . . . , Bk, . . . , BMxe2x88x921) with a vector formed of an M-bit output sequence after diffusion:
(Bxe2x80x20, Bxe2x80x21, . . . , Bxe2x80x2n, . . . , Bxe2x80x2Mxe2x88x921), where Bxe2x80x2n=Bk (n=k+s mod M).
The bit diffusion circuits 5-1 and 5-2 may use the same algorithm with different values of s.
Data sequences xxe2x80x2 and yxe2x80x2 after bit diffusion, constituting a diffused punctured convolutional code message, are output from the bit diffusion circuits 5-1 and 5-2, and input to a signal point assignment circuit 6.
Signal point assignment circuit 6 outputs coordinate data Ixe2x80x2 and Qxe2x80x2 of signal points representing an in-phase component (I component) and a quadrature component (Q component) orthogonal to each other. For example, the assignment of data (xxe2x80x2, yxe2x80x2) as signals in the transmission channel is performed on the basis of the quadrature phase shift keying (QPSK) symbol set as shown in FIG. 12. That is, the data is assigned so that
when (xxe2x80x2, yxe2x80x2)=(0, 0), (Ixe2x80x2, Qxe2x80x2)=(1/{square root over (2)},1/{square root over (2)}) is set;
when (xxe2x80x2, yxe2x80x2)=(0, 1), (Ixe2x80x2, Qxe2x80x2)=(1/{square root over (2)},xe2x88x921/{square root over (2)}) is set;
when (xxe2x80x2, yxe2x80x2)=(1, 0), (Ixe2x80x2, Qxe2x80x2)=(xe2x88x921/{square root over (2)},1/{square root over (2)}) is set; and
when (xxe2x80x2, yxe2x80x2)=(1, 1), (Ixe2x80x2, Qxe2x80x2)=(xe2x88x921/{square root over (2)},xe2x88x921/{square root over (2)}) is set. Each set of components (Ixe2x80x2,Qxe2x80x2) constitutes one QPSK symbol. Each such symbol includes a first component Ixe2x80x2 denoting the value of one bit xxe2x80x2 in the diffused punctured convolutional code message and a second component Qxe2x80x2 denoting the value of another bit yxe2x80x2 in the diffused punctured convolutional code message.
A symbol diffusion circuit 7 reorders the QPSK symbols prescribed by data Ixe2x80x2 and Qxe2x80x2 output from the signal point assignment circuit 6 to obtain symbols S (I, Q). This diffusion processing increases resistance of the system to burst errors in the transmission path. The diffusion circuit changes the order of symbols Sxe2x80x2 represented by (Ixe2x80x2, Qxe2x80x2) in accordance with a predetermined rule to obtain the diffused symbols S represented by (I,Q).
For example, if Nxe2x88x921 symbols form a diffusion unit block and if a number G smaller than N is selected such that G and N are prime to each other, diffusion is executed as replacement of a vector formed of symbols before diffusion:
(Sxe2x80x21, Sxe2x80x22, . . . , Sxe2x80x2k, . . . , Sxe2x80x2Nxe2x88x921) with a vector formed of symbols after diffusion:
(S1, S2, . . . , Sn, . . . , SNxe2x88x921), where Sn=Sxe2x80x2k (n=G{circumflex over ( )}k mod N). In this expression, G{circumflex over ( )}k means G to the kth power.
Diffusion circuit 7 outputs the I and Q components of the symbols after symbol diffusion. A modulator 8 modulates a carrier wave with the I and Q components of symbols S on the basis of the orthogonal frequency division multiplex (OFDM) method and transmits the modulated wave through an antenna 9.
FIG. 13 shows the configuration of a receiver for receiving data from the transmitter shown in FIG. 9. A demodulator 32 demodulates an electric wave received through an antenna 31 and outputs a series of signals, corresponding to the series of symbols supplied to the modulator 8 of the transmitter. Each such signal includes an I component and a Q component corresponding to the I and Q components of the transmitted symbols. It should be appreciated that the I and Q components of the signals output by demodulator are not perfect duplicates of the I and Q values supplied to modulator of the transmitter. Noise and other imperfections in the transmission path cause variations in the received I and Q values. The I and Q values constituting the received signals are handled in the receiver as real values, i.e., either as analog values or, preferably, as multi-bit digital values. Demodulator 32 supplies the received signals as series of I and Q components.
A symbol diffusion reversal circuit 33 processes the received signals in a manner inverse to the symbol diffusion processing in the symbol diffusion circuit 7 of the transmitter ( FIG. 9). Thus, the diffusion reversal circuit restores the received signals to the original order of the symbols before the order was changed in the symbol diffusion circuit 7. This diffusion reversal operation, if expressed by using the same N and G as those used with respect to the symbol diffusion circuit 7, is replacement of a vector formed of signals before diffusion reversal processing:
(S1, S2, . . . , Sn, . . . , SNxe2x88x921) with a vector formed of signals after diffusion reversal processing:
(Sxe2x80x21, Sxe2x80x22, . . . , Sxe2x80x2k, . . . , Sxe2x80x2Nxe2x88x921), where Sn=Sxe2x80x2k (n=G{circumflex over ( )}k mod N).
I component values Ixe2x80x2 and Q component values Qxe2x80x2 output from the symbol diffusion reversal circuit 33 are supplied to bit diffusion reversal circuits 34-1 and 34-2, respectively. The bit diffusion reversal circuits process the Ixe2x80x2 and Qxe2x80x2 components output in a manner inverse to the bit diffusion applied by the bit diffusion circuits 5-1 and 5-2 of the transmitter. Thus, bit diffusion reversal circuit 34-1 processes items of data (I component values) in blocks of M items. A vector formed of a sequence of output M items after diffusion reversal processing:
(B0, B1, . . . , Bk, . . . , BMxe2x88x921) is obtained from a vector formed of a sequence of input M items:
(Bxe2x80x20, Bxe2x80x21, . . . , Bxe2x80x2n, . . . , Bxe2x80x2Mxe2x88x921), where Bxe2x80x2n=Bk (n=k+s mod M).
The value s used in bit diffusion reversal processing in the bit diffusion reversal circuit 34-1 is the same as the value s used in the bit diffusion circuit 5-1 of the transmitter. Bit diffusion reversal circuit 34-2 operates in the same manner, but uses a value s equal to the value s used by the other bit diffusion reversal circuit 5-2.
The two data sequences (x, y) output from the bit diffusion reversal circuits 34-1 and 34-2 are input to a parallel-serial converter 35 to be converted into one data sequence to be supplied to a bit insertion circuit 36. The parallel-serial converter 35 performs the operation reverse to that of the serial-parallel converter 4 to convert the two data sequences (x, y) into one data sequence.
The bit insertion circuit 36 splits the serial data stream into two parallel data streams and performs bit insertion processing inverse to the bit erase processing in the bit erase circuit 3 shown in FIG. 9. The bit insertion circuit 36 uses the same map used by the bit erase circuit of the transmitter:
X: 10
Y: 11
Thus, when data is input in the order of x1, y1, y2 to insertion circuit 36, an arbitrary dummy data item (here assumed to be 0) is inserted at the position corresponding to the erased data item and
X1 (=x1 ), 0 are output as X data, and
Y1 (=y1), Y2 (=y2) are output as Y data in this order.
The output data sequences X and Y are supplied to a Viterbi decoder 37. Also, an insertion flag indicating the position at which the dummy data is inserted is supplied to the Viterbi decoder 37. At this stage of processing, the individual data elements of sequences X and Y (other than the dummy values) are still real numbers corresponding to the values of the I and Q components in the received signals, rather than single-bit 1 or 0 elements. The real numbers in these data sequences correspond to the 1 and 0 values of the mother codes output by the convolutional encoder 2 of the transmitter. If the transmission channel were a perfect channel, each number corresponding to a 0 in the mother code would have exactly the same value, equal to the nominal value 1/{square root over (2)} assigned by the signal point assignment circuit of the transmitter, whereas each number corresponding to a 1 in the mother code would have the other nominal value xe2x88x921/{square root over (2)}. However, noise and other imperfections in the transmission path between the transmitter and receiver will cause these values to vary somewhat from the nominal values.
The Viterbi decoder 37 decodes the data sequences X and Y to recover the reproduced information corresponding to the original message. Thus, the decoder performs Viterbi decoding according to the state transitions (FIG. 11) of the convolutional encoder 2.
FIG. 14 shows an example of the Viterbi decoder 37. Data X and Y output from the bit insertion circuit 36 are supplied to input terminals 62-1 and 62-2 respectively for input to branch metric calculation circuits 63-1 to 63-4. Each of the branch metric calculation circuits 63-1 to 63-4 calculates, as a branch metric, the distance between the input data (X, Y) and an associated one of the coordinate points defined by nominal values shown in FIG. 12.
Outputs (branch metrics) BM00 and BM11 from the branch metric calculation circuits 63-1 and 63-4 are input to add compare select (ACS) circuits 64-1 and 64-3. A output (branch metric) BM01 from the branch metric calculation circuit 63-2 and an output (branch metric) BM10 from the branch metric calculation circuit 63-3 are input to ACS circuits 64-2 and 64-4.
Four state metric storage units 66-1 through 66-4 are provided. State metric storage unit 66-1 has an input 66-1a connected to an output of ACS unit 64-1. In like manner, each of the other state metric storage units 66-2, 66-3 and 66-4 has an input connected to the outputs of ACS units 64-2, 64-3 and 64-4, respectively.
An output (state metric) SM00 from state metric storage 66-1 and an output (state metric) SM01 from state metric storage 66-2 are also input to the ACS circuits 64-1 and 64-3. An output (state metric) SM10 from state metric storage 66-3 and an output (state metric) SM11 from state metric storage 66-4 are also input to the ACS circuits 64-2 and 64-4.
Each of the ACS circuits 64-1 to 64-4 calculates the sum of one of the input branch metrics BM and the corresponding state metric SM and calculates the sum of the other input branch metric BM and the corresponding state metric SM. Each of the ACS circuits 64-1 to 64-4 compares the two sums with each other to select the smaller one of them, outputs the smaller sum as a new state metric SM to the corresponding one of the state metric storage units 66-1 to 66-4, and outputs signals SEL00 to SEL11 representing the selection result to a path memory 65. State metrics SM00 to SM11 from the state metric storages 66-1 to 66-4 are also input to the path memory 65.
Each of the state metric storages 66-1 to 66-4 can be reset by a signal which is input via a terminal 61. The path memory 65 outputs the result of decoding through a terminal 67.
The operation of the Viterbi decoder 37 will be described in more detail. Branch metric calculation circuit 63-1 calculates the distance between the input data (X, Y) and the coordinate point (1/{square root over (2)},1/{square root over (2)}) as branch metric BM00. Similarly, branch metric calculation circuit 63-2 calculates the distance between the input data (X, Y) and the coordinate point (1/{square root over (2)},xe2x88x921/{square root over (2)}) as branch metric BM01. Branch metric calculation circuit 63-3 calculates the distance between the input data (X, Y) and the coordinate point (xe2x88x921/{square root over (2)},1/{square root over (2)}) as branch metric BM10. Branch metric calculation circuit 63-4 calculates the distance between the input data (X, Y) and the coordinate point (xe2x88x921/{square root over (2)},xe2x88x921/{square root over (2)}) as branch metric BM11. In computing the branch metrics, distance calculation with respect to the inserted dummy data is omitted in response to the insertion flag supplied from the bit insertion circuit 36. That is, the distance between each inserted dummy data value and the related coordinate point is set to a zero value as further discussed below with reference to FIG. 15.
ACS circuit 64-1 performs two calculations shown below corresponding to the state transitions of the convolutional encoder 2, and selects one of the results of these calculations with a higher likelihood, i.e., the smaller one of the calculation results. Information SEL00 on this selection is supplied to the path memory 65 while the calculation result is SM00 is supplied to the state metric storage 66-1.
SM00+BM00xe2x80x83xe2x80x83(1)
SM01+BM11xe2x80x83xe2x80x83(2)
SM00 is the value of the state metric storage 66-1 remaining from the preceding clock cycle, i.e., the value of the state metric resulting from processing the preceding X and Y values in the data sequence. Similarly, SM01 is the value remaining in state metric storage 66-2 from the preceding clock cycle. BM00 is the result of calculation of the branch metric calculation circuit 63-1, and BM11 is the result of calculation of the branch metric calculation circuit 63-4.
If the result of calculation (1) is smaller, SEL00=0 is supplied to the path memory 65. If the result of calculation (2) is smaller, SEL00=1 is supplied to the path memory 65. In the former case, SM00+BM00 is stored as new state metric SM00 in the state metric storage 66-1. In the latter case, SM01+BM11 is stored as new state metric SM00 in the state metric storage 66-1.
This calculation will be described with reference to the state transition diagram of FIG. 11. The branch metrics can be understood as representing the likelihood that the input data (X,Y) represents the mother code bits produced by a transition of the convolutional encoder which resulted in particular outputs. For example, if input data X,Y having values very close to the nominal values (1/{square root over (2)},1/{square root over (2)}) is received, and hence the magnitude of BM00 is small, then it is likely that the input data was produced by a transition of the convolutional encoder 2 at the transmitter which produced outputs (mother code bits X,Y) of 00. The state metrics can be understood as representing the probability that the convolutional encoder 2 at the transmitter which produced the data was in a particular state, with smaller values of the state metrics representing greater probability. For example, a smaller value of SM00 indicates a high probability that the encoder was in state 00. There are two paths to the state 00. The first path is defined by input of 0 in the state 00 and by output of 00. A corresponding comparative calculation is represented by expression (1). The second path is defined by input of 0 in the state 01 and by output of 11. A corresponding comparative calculation is represented by expression (2). The smaller one of the two calculation results is supplied as new state metric SM00 to the state metric storage 66-1.
Each of the ACS circuits 64-2 to 64-4 also performs the same operation. Each of the state metric storages 66-1 to 66-4 is reset to 0 in an initial stage of the operation of the system. Control of this resetting is performed by a controller (not shown) via the terminal 61.
Path memory 65 generates the reproduced data which is the final output of the receiver, in accordance with the state transitions shown in FIG. 11. The path memory uses selection information SEL00 to SEL11 supplied from the ACS circuits 64-1 to 64-4 and the state metrics SM00 to SM11 supplied by state metric storage units 66-1 to 66-4.
FIG. 15 shows a branch metric calculation circuit 63-1 in detail. Data X input through the terminal 62-1 is input to a subtracter circuit 51, which subtracts 1/{square root over (2)} supplied from a generator circuit 52 from data X. The difference output from the subtracter circuit 51 is supplied to two input terminals of a multiplier circuit 53 and multiplied by itself (i.e., squared). A selector 203 is supplied with an output from the multiplier circuit 53 and with a 0 output from a generator circuit 202. When the flag indicating insertion in X is input to the selector 203 from bit insertion circuit 36 (FIG. 13) via a terminal 201, the selector 203 selects the 0 generated by the generator circuit 202. When no flag indicating insertion in X is input, the selector 203 selects the output from the multiplier circuit 53. The selector 203 outputs the selected value to an adder circuit 54.
Data Y input via the terminal 62-2 is input to a subtracter circuit 55, which subtracts 1/{square root over (2)} supplied from a generator circuit 56 from data Y. The output from subtracter circuit 56 is supplied to two input terminals of a multiplier circuit 57 to be multiplied by itself (i.e., squared). A selector 206 is supplied with an output from the multiplier circuit 57 and with an output from a 0 generator circuit 205. When the flag indicating insertion in Y is input to the selector 206 via a terminal 204, the selector 206 selects 0 from circuit 205. When no flag indicating insertion in Y is input, the selector 206 selects the output from the multiplier circuit 57. The selector outputs the selected value to adder circuit 54. The adder circuit 54 calculates the sum of the outputs from the selectors 203 and 206 and outputs the sum as branch metric BM00.
Thus, when no insertion flag is supplied, the operation of this branch metric calculation circuit is as described below. The subtracter circuit 51 outputs Xxe2x88x921/{square root over (2)}, and the multiplier circuit 53 squares this value to output (Xxe2x88x921/{square root over (2)})2. Also, the subtracter circuit 55 outputs Yxe2x88x921/{square root over (2)}, and the multiplier circuit 57 squares this value to output (Yxe2x88x921/{square root over (2)})2. The adder circuit 54 calculates the sum of the outputs from the multiplier circuits 53 and 57, i.e.,(Xxe2x88x921/{square root over (2)})2+(Yxe2x88x921/{square root over (2)})2 and outputs this value as branch metric BM00.
On the other hand, when the flag indicating insertion in X is input, the selector 203 outputs 0, so that the output from the adder circuit 54 is (Yxe2x88x921/{square root over (2)})2. When the flag indicating insertion in Y is input, the selector 206 outputs 0 and the output from the adder circuit 54 is (Xxe2x88x921/{square root over (2)})2.
Each of the branch metric calculation circuits 63-2 to 63-4 have the same circuit configuration as that shown in FIG. 15 and performs the same operation. In the branch metric calculation circuit 63-2, however, the output of the generator circuit 52 is 1/{square root over (2)} and the output of the generator circuit 56 is xe2x88x921/{square root over (2)}. In the branch metric calculation circuit 63-3, the outputs of the generator circuits 52 and 56 are xe2x88x921/{square root over (2)} and 1/{square root over (2)}, respectively. In the branch metric calculation circuit 63-4, the output of each of the generator circuits 52 and 56 is xe2x88x921/{square root over (2)}.
FIG. 16 is a block diagram of the path memory 65. Selection information items SEL00 to SEL11 output from the ACS circuits 64-1 to 64-4 are supplied to terminals 71-1 to 71-4. The selection information items SEL00 to SEL11 are input as control signals to two-input one-output selectors 73-1 to 73-4, respectively. A fixed data item 0 is supplied from a terminal 72-1 as two inputs to the selector 73-1, whereas fixed data item 0 is supplied from terminal 72-2 as the two inputs of selector 73-2. Similarly, a fixed data item 1 is supplied from terminals 72-3 and 72-4 as two inputs to each selector 73-2 to 73-4.
Each of the selectors 73-1 to 73-4 selects one of the two inputs according to the corresponding one of the selection information items SEL00 to SEL11 and outputs the selected data item to the corresponding one of registers 81-1 to 81-4. As mentioned above the same data item from one of the terminals 72-1 to 72-4 is input as two inputs to the corresponding one of the first-column selectors 73-1 to 73-4. Therefore, the first-column registers 81-1 to 81-4 store 0, 0, 1, and 1, respectively.
Other selectors and registers are arranged in the same manner as those described above; the selectors and registers are arranged in n columns (four columns in the example shown in FIG. 16). That is, in the second column, selectors 74-1 to 74-4 and registers 82-1 to 82-4 are provided. Outputs from first-column registers 81-1 and 81-2 are supplied to the selectors 74-1 and 74-3 in the second column. Outputs from first-column registers 81-3 and 81-4 are supplied to second-column selectors 74-2 and 74-4. Each of the second-column selectors 74-1 to 74-4 performs processing such as to select one of the two inputs according to the value of the corresponding one of the selection information items SEL00 to SEL11 and to output the selected data item to the corresponding one of the second column registers 82-1 to 82-4. For example, register 74-1 selects the output of register 81-1 when selection information item SEL00 is 0, selects the output of register 81-2 when selection information item SEL00 is 1, and outputs the selected data item to register 82-1. The third and fourth column selectors and registers operate in a similar manner.
Outputs from registers 84-1 to 84-4 in the final column are input to a four-input one-output selector 85. State metrics SM00 to SM11 output from the state metric storages 66-1 to 66-4 shown in FIG. 14 are input to a minimum value comparator circuit 88. The minimum value comparator circuit 88 compares the four state metrics and selects the smallest of them. The minimum value comparator circuit 88 outputs data 00 if the state metric SM00 is the smallest, data 01 if the state metric SM01 is the smallest, data 10 if the state metric SM10 is the smallest, and data 11 if the state metric SM11 is the smallest. The selector 85 selects the output of the register 84-1 when the input from the minimum value comparator circuit 88 is 00, the output of the register 84-2 when the input from the minimum value comparator circuit 88 is 01, the output of the register 84-3 when the input from the minimum value comparator circuit 88 is 10, and the output of the register 84-4 when the input from the minimum value comparator circuit 88 is 11. The output from the selected register is output by selector 85 as a decoding result through a terminal 86. The sequence of outputs from terminal 86 represents the reproduced information.
The above-described connections in the path memory 65 provide outputs corresponding to the state diagram of FIG. 11. The fixed values (0 and 1) at terminals 72-1 to 72-4 represent possible decoded information items. The values which will propagate through the matrix of selectors and registers will depend on the values of selection information SEL00 through SEL11. Those values in turn depend on the values of the state metrics and branch metrics during each clock cycle as discussed above. In effect, the data items which appear at the final registers 84-1 through 84-4 are associated with different possible paths through the trellis or sequence of states of the convolutional encoder. The data item corresponding to the path with the maximum likelihood is selected from the four data items stored in registers 84-1 through 84-4 of the final column, and the selected item is output as the reproduced information. The selector 85 selects the item corresponding to the state metric minimum value, i.e., the path with the maximum likelihood, at each time point. Stated another way, the Viterbi decoder yields a sequence of reproduced data which represents the most likely sequence of original data input to the convolutional encoder at the transmitter. In choosing the most likely sequence, the decoder selects each bit of the reproduced data on the basis of several bits of transmitted data. This provides substantial coding gain.
The increasing demand for high speed data transmission makes it desirable to extend the digital data transmission system described above from the QPSK implementation to other, more complex modulation systems. In the more complex transmission schemes, each transmitted signal denotes values for more than two bits. Each signal typically includes two components, each component having more than two possible nominal values. Examples of such modulation systems include 16-QAM, 64-QAM, and 256-QAM. In the 16-QAM system, each symbol includes two components, and each component has four possible nominal values, so that any one of 16 possible symbols can be transmitted. Thus, each symbol can denote values for four bits. The 64-QAM and 256-QAM systems use symbol sets with 64 and 256 possible symbols to encode six and eight bits per symbol, respectively. By comparison, in the QPSK system described above, only two bits are encoded in each symbol. The more complex transmission systems offer the possibility of higher data transmission rates. However, it is difficult to use an encoding and decoding strategy with convolutional or punctured convolutional coding and with bit diffusion as described above in combination with a multi-component, multi-value modulation system.
FIG. 17 depicts a data transmitter using 16-QAM. In FIG. 17, sections corresponding to the QPSK transmitter of FIG. 9 are indicated by the same reference numerals. The convolutional encoder 2 and bit erase circuit 3 are identical to those used in the QPSK transmitter, and produce a punctured convolutional code sequences identical to that discussed above. However, the serial-parallel converter 4 of FIG. 17 splits the serial data output from bit erase circuit 3 into four parallel data streams u, v, x, and y. These data items in each undergo bit diffusion processing in bit diffusion circuits 91-1 to 91-4 to yield reordered data uxe2x80x2, vxe2x80x2, xxe2x80x2, and yxe2x80x2, which are supplied to a signal point assignment circuit 6. The bit diffusion processing applied to each data sequence is the same as that applied in the bit diffusion circuits 5-1 and 5-2 of FIG. 9. The bit diffusion processing is varied with respect to the data sequences by using different values s for each data sequence.
The signal point assignment circuit 6 assigns input 4-bit data (uxe2x80x2, vxe2x80x2, xxe2x80x2, yxe2x80x2) as symbols of the 16-QAM symbol set shown in FIG. 18. In the 16-QAM set, each symbol includes two components Ixe2x80x2 and Qxe2x80x2. Each component can have any one of four nominal values, and each component denotes values of two bits. Thus, component Ixe2x80x2 denotes the values of the first and third bits of the 4-bit data, whereas component Qxe2x80x2 denotes the values of the second and fourth bits. For example,
(Ixe2x80x2, Qxe2x80x2)=(3/{square root over (10)},3/{square root over (10)}) when (uxe2x80x2, vxe2x80x2, xxe2x80x2, yxe2x80x2)=(0, 0, 0, 0), and
(Ixe2x80x2, Qxe2x80x2)=(3/{square root over (10)},1/{square root over (10)}) when (uxe2x80x2, vxe2x80x2, xxe2x80x2, yxe2x80x2)=(0, 0, 0, 1).
The symbols produced by signal point assignment circuit 6 are subjected to symbol diffusion in a symbol diffusion circuit 7 in the same manner as discussed above, and the reordered components I and Q are supplied to a modulator 9 and transmitted by OFDM modulation as discussed above. In other respects, the configuration of the transmitter shown in FIG. 17 is the same as that shown in FIG. 9.
A receiver for the 16-QAM signal from the transmitter of FIG. 17, constructed in a manner analogous to the QPSK receiver of FIG. 13, would have the structure shown in FIG. 19. However, a receiver as shown in FIG. 19 will not operate properly.
In the QPSK system as described above with reference to FIG. 13, each of the signal components I and Q input from the symbol diffusion reversal circuit 33 to the bit diffusion reversal circuits 34-1 and 34-2 represents one bit of the bit-diffused punctured convolutional code message. Therefore, reordering of the I and Q signal components by the bit diffusion reversal circuits, in a manner inverse to the reordering applied by the bit diffusion circuits of the transmitter, will restore the signal components to the same order as the order of the bits in the message before bit diffusion processing. However each of components I and Q in the 16-QAM system represents two bits. In the symbol set or signal point constellation shown in FIG. 18, I includes information of the first and third bits while Q includes information of the second and fourth bits. However, I is one value such as 1/{square root over (10)} or 3/{square root over (10)}, and Q is also such one value. If the stream of I and Q component values is simply divided into four data streams as shown in FIG. 19, each data item in each data stream uxe2x80x2, vxe2x80x2, xxe2x80x2and yxe2x80x2 still represents two bits, rather than a single bit. Applying diffusion reversal processing in circuits 95-1 to 95-4, inverse to the bit diffusion processing applied to single-bit data items by transmitter bit diffusion circuits 91-1 to 91-4 (FIG. 17) will scramble the data; it will not recover the original order. Stated another way, the bit diffusion operation is performed at the transmitter on single-bit data, but the signal component values I and Q represent two bits each. Therefore, the inverse operation cannot be performed on the I and Q component values at the receiver.
The same problem arises in connection with the bit erase and bit insertion operations. Thus, the bit erase circuit 3 of the transmitter in FIG. 17 operates on single bits of the mother code. Operation of the bit insertion circuit 36 to insert dummy data into a stream of two-bit component values will further scramble the data and will not restore the original structure of the data. The result of Viterbi decoding of the output from the bit insertion circuit 36 by the Viterbi decoder 37 would be completely different from the original data.
It would appear that the problems associated with handling component values representing multiple bits could be obviated by recovering the individual bit values at or immediately after the symbol diffusion reversal circuit 33 of the data receiver shown in FIG. 19. Thus, prior to the bit diffusion reversal circuit, the I and Q components of each signal can be evaluated to yield the individual bit values uxe2x80x2, vxe2x80x2, xxe2x80x2 and yxe2x80x2. In such a case, the distances between the coordinates (I, Q) defined by the I and Q components of each received signal and the nominal signal points shown in FIG. 18 are calculated. The received signal is deemed to represent the symbol associated with the closest nominal signal point, and bit values are assigned on the basis of that symbol. For example, a received signal having I and Q coordinates close to coordinates (xe2x88x921/{square root over (10)},3/{square root over (10)}) is deemed to represent the symbol having nominal values (xe2x88x921/{square root over (10)},3/{square root over (10)}), i.e., 1010 in FIG. 18. The bit values associated with this symbol are assigned to the 4-bit data; uxe2x80x2=1, vxe2x80x2=0, xxe2x80x2=1 and yxe2x80x2=0. The bit values recovered in this manner are single-bit values and can be processed through bit diffusion reversal and bit insertion.
However, such a system makes a xe2x80x9chardxe2x80x9d decision as to the value of each bit based on the content of a single received signal. It sacrifices the advantages of noise immunity and coding gain obtained by xe2x80x9csoftxe2x80x9d decoding, such as the Viterbi decoding discussed above, in which information transmitted in several signals, during several unit times, contributes to the decision made by the receiver as to the most probable value for each bit of the reproduced information.
Similar problems arise in other multi-value, multi-component modulation systems such 64-QAM or 256-QAM. Thus there has been a need for improved receiving apparatus and methods which can accurately receive and decode data transmitted by a multi-value, multi-component modulation system can be accurately decoded.
One aspect of the present invention provides a data receiver for receiving data which includes a series of received multi-component signals representing symbols selected from a set of possible multi-component, multi-value symbols wherein signal denotes values for more than two bits. Typically, each component denotes values for a plurality of bits. The data receiver includes probability calculation means for calculating, from components of each received signal, probabilities that different possible symbols of the symbol set constituted the transmitted symbol represented by the received signal. The receiver further includes bit metric calculation means for calculating bit metrics for the bits denoted by each received signal. The bit metric calculation means may be arranged to calculate a bit metric for a particular bit from the probabilities calculated by the probability calculation means for those possible symbols which denote a predetermined value of that particular bit. For example, in the 16-QAM system discussed above, the probability calculation means preferably calculates, from the I and Q components of each received signal, the probability that each of the symbols shown in FIG. 18 was transmitted.
The probability that each symbol was transmitted may be calculated as a function of the distance between the coordinates defined by the components of the received signal and the coordinates defined by the nominal component values of each symbol. The bit metric calculation means may be arranged to calculate the sum of the probabilities of all of the symbols denoting the predetermined value for the bit in question. For example, to calculate the bit metric for the first bit in the 16-QAM system, the system may calculate the sum of the probabilities for all of the symbols denoting a first-bit value of 0, i.e., for all of the symbols having I-component values of 1/{square root over (10)} or 3/{square root over (10)}. To calculate the bit metric for the fourth bit, the bit metric calculation means may calculate the sum of the probabilities for all of the symbols denoting a fourth-bit value of 0, i.e., all of the symbols in which the Q-component value is 3/{square root over (10)} or xe2x88x923/{square root over (10)}. Other composites of the probabilities, and other functions of the sum of probabilities can be used instead of the simple sum.
Because each bit metric represents a single bit of transmitted data, the bit metrics can be handled and subjected to processes such as bit diffusion reversal and bit insertion inverse to the bit diffusion and bit erasure processes applied to single-bit data at the transmitter. The receiver may include means for forming sequences of bit metrics and reordering the bit metrics so as to reverse a bit diffusion operation applied at the transmitter. The receiver may further include means for inserting dummy values into a sequence of bit metrics, thereby reversing a bit erasure operation at the transmitter. However, the bit metrics are not xe2x80x9chardxe2x80x9d 1 or 0 values for individual bits. Rather, the bit metric represents the probability that the transmitted symbol included the predetermined value for that particular bit 0 in the examples given above. The bit metrics are real number values, similar to the real values which are propagated through the various stages of the QPSK receiver and presented to the Viterbi decoder as discussed above with reference to FIG. 13. These real values can be used in a xe2x80x9csoftxe2x80x9d decoding scheme, such as Viterbi decoding, in which the receiver decides on the most probable value of each bit in the reproduced information based on information contained in several bits sent through the transmission channel. Thus, the receiver preferably is adapted to receive signals representing transmitted data encoded in a convolutional code, and has decoding means including means for deconvoluting inverse to the convolutional code. The means for deconvoluting preferably includes means for deconvoluting according to a most-likely path decoding scheme such as a Viterbi decoder.
As mentioned above, functions of the sum of probabilities other than the sum itself may be employed. For example, the bit metric may be calculated as the product of xe2x88x921 and the logarithm of the aforementioned sum of probabilities. According to a further embodiment of the invention, the bit metric calculation means may be operative to calculate a first sum representing the probabilities of transmission of all of the possible symbols in the symbol set and may be arranged to calculate a second sum including only the probabilities of transmission of the symbols having a component denoting the predetermined value of the bit in question. The bit metric calculation means may be arranged to obtain the bit metric for the particular bit by dividing the second sum by the first sum. As further explained below, the quotient so obtained is the value of the conditional posterior probability that the transmitted symbol denoted the predetermined value of the particular bit.
A data receiver according to a further aspect of the present invention is also adapted to receive the multi-component signals representing symbols selected from a set of possible symbols in a multi-component, multi-value symbol set. A receiver according to this aspect of the invention includes a memory having stored therein a set of bit metrics for bits having predetermined values in the transmitted signal. Different bit metrics are stored at different addresses in the memory. The receiver according to this aspect of the invention also includes reading means for selecting one or more addresses in the memory for each received signal based on the components of that received signal and reading out of the memory the bit metric stored at each selected address. Preferably, the reading means and the stored set of bit metrics are arranged so that, for any received signal, the bit metric read out from the memory will be substantially equal to the bit metric found by calculating, from the received signal, probabilities that different symbols were transmitted and calculating a bit metric from the calculated probabilities for those symbols having a component denoting the predetermined value of the bit. Thus, preferred receivers according to this aspect of the invention derive the bit metrics by use of a xe2x80x9clookup tablexe2x80x9d approach rather than by direct calculation, but arrive at substantially the same values of the bit metrics as used in the above-mentioned aspect of the invention.
Further aspects of the present invention provide methods of receiving multi-component, multi-value signals representing symbols of a multi-component, multi-value symbol set. The method may include the steps of calculating, from the components of each received signal, probabilities that different possible symbols constituted the transmitted symbol and calculating bit metrics for the bits denoted by the received signal from the probabilities calculated for those possible symbols denoting the predetermined value of the bit. The steps of calculating the probabilities may be performed by determining the distance between the coordinates defined by the components of the received signal and the coordinates defined by the nominal component values of each symbol. The step of calculating the bit metrics may be performed by calculating a sum of the probabilities for those symbols denoting a predetermined value of a bit, as discussed above in connection with the receiver. Other methods according to other aspects of the invention include the steps of selecting at least one address in a memory for each received signal based upon the components of the signal and reading out one or more bit metrics stored at the selected address or addresses in the memory. As discussed above in connection with the receiver, different bit metrics are stored at different addresses in the memory, so that different received signals having different components will cause different bit metrics to be read out of the memory. The arrangement of the stored bit metrics in the memory, and the way in which the address is selected based upon the received components, desirably are selected so that the bit metrics read out from the memory will be equivalent to those arrived at by calculation.
Methods in accordance with the foregoing aspects of the invention desirably further include the steps of processing the bit metrics and recovering reproduced data from the processed bit metrics. Most preferably, the bits represented by the received signals include transmitted data which constitutes the original data encoded in a convolutional code. The processing step most preferably includes the step of deconvoluting the bit metrics in a manner inverse to the convolutional code. The deconvoluting step desirably is performed so as to provide a xe2x80x9csoftxe2x80x9d or most-likelihood decoding, in which the value of each bit in the reproduced data depends upon the value of several bits in the transmitted data. The processing step may include the steps of forming one or more streams of bit metrics and subjecting the bit metrics streams to bit diffusion reversal processing, bit insertion processing or both. As discussed above in connection with the apparatus, the methods allow the use of multi-value, multi-component transmission schemes, while maintaining all of the advantages afforded by bit diffusion, bit erasure and soft decoding.
The foregoing and other objects, features and advantages of the present invention will be more readily apparent from the detailed description of the preferred embodiments set forth below, taken in conjunction with the accompanying drawings.